package com.geek.spring.algorithms.link;


import org.junit.Test;
import org.w3c.dom.Node;

import java.util.HashSet;
import java.util.Set;

import static org.junit.Assert.assertEquals;

/**
 * @program java-spring
 * @description: List
 * @author: chanzhugang
 * @create: 2021/08/19 17:04
 */
public class List<T> {

    // 节点数据、next指针
    static class Node<T> {
        Node<T> next = null;

        T data;

        public Node(T data) {
            this.data = data;
        }
    }

    // 头节点
    Node<T> head = null;


    // 头插法
    public void insert(T data) {
        Node<T> node = new Node<>(data);
        node.next = head;
        head = node;

    }

    // 链表反转： 三指针偏移法： 每遍历一次，指针反转一次， 节点往后偏移一次
    public void reverse() {
        Node<T> prev = null;
        Node<T> current = head;
        Node<T> next = null;

        while (current != null) {
            next = current.next;
            // 指针反转一次
            current.next = prev;
            // 往后偏移一位
            prev = current;
            current = next;
        }
        // current == null， head 指向prev
        head = prev;

    }

    // 判断链表是否有环: Set 方法
    public boolean hasLoop() {
        Set<Node> set = new HashSet<>();

        Node<T> p = head;
        while (p != null) {
            if (set.contains(p)) {
                return true;
            }
            set.add(p);
            p = p.next;
        }
        return false;


    }

    // 快慢指针方法： 隔两个节点:
    public boolean hasLoop2() {
        if (head == null || head.next == null) {
            return false;
        }
        Node<T> slow = head;
        Node<T> fast = head.next.next;
        while (fast != null && fast.next != null) {
            if (fast == slow) {
                // 快指针是否追上慢指针
                return true;
            }
            slow = fast;
            fast = fast.next.next;
        }
        return false;

    }




}